package com.cn.algorithm02.class12;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/***
 * @author: hels
 * @description: 序列化和反序列化： 层和先序两种序列化方法
 **/
public class C02_Serialize {
    public static void main(String[] args) {
        Node d = new Node("d", null, null);
        Node c = new Node("c", d, null);
        /*Nodea b1 = new Nodea("b1", null, null);
        Nodea b2 = new Nodea("b2", null, null);*/
        Node b = new Node("b", null, null);
        Node a = new Node("a", b, c);

        Queue<String> strings = posSerial(a);
        System.out.println(strings);

        Node node = posDeserial(strings);


        System.out.println("============");
        System.out.println(node);
        System.out.println(node.left);
        System.out.println(node.left.left);
        System.out.println(node.right);
        System.out.println(node.right.left);
    }

    // 先序序列化
    public static Queue<String> preSerial(Node head) {
       Queue<String> ans = new LinkedList<>();
       preS(head, ans);
       return ans;
    }
    private static void preS(Node head, Queue<String> ans) {
        if (head == null) {
            ans.add(null);
        } else {
            ans.add(head.value);
            preS(head.left, ans);
            preS(head.right, ans);
        }
    }

    // 先序反序列化 中左右
    public static Node preDeserial(Queue<String> preList) {
        if (preList == null || preList.size() == 0) return null;
        return preDes(preList);
    }
    private static Node preDes(Queue<String> preList) {
        String value = preList.poll();
        if (value == null) return null;

        Node head = new Node(value, null, null);
        head.left = preDes(preList);
        head.right = preDes(preList);
        return head;
    }

    // 后序：序列化, 左右中
    public static Queue<String> posSerial(Node head) {
        Queue<String> ans = new LinkedList<>();
        posS(head, ans);
        return ans;
    }
    private static void posS(Node head, Queue<String> ans) {
        if (head == null) {
            ans.add(null);
        } else {
            posS(head.left, ans);
            posS(head.right, ans);
            ans.add(head.value);
        }
    }

    // 后续：反序列化， 左右中 --Stack--》 中右左
    public static Node posDeserial(Queue<String> posList) {
        if (posList == null || posList.size() == 0) return null;
        Stack<String> stack = new Stack<>();
        while (!posList.isEmpty()) {
            stack.push(posList.poll());
        }
        return posDes(stack);
    }

    private static Node posDes(Stack<String> stack) {
        String value = stack.pop();
        if (value == null) {
            return null;
        } else {
            Node node = new Node(value, null, null);
            node.right = posDes(stack);
            node.left = posDes(stack);
            return node;
        }
    }

    // 按层序列化
    public static Queue<String> levelS(Node head) {
        if (head == null) return null;

        Queue<String> ans = new LinkedList<>();
        Queue<Node> queue = new LinkedList<>();
        ans.add(head.value);
        queue.add(head);
        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            if (cur.left != null) {
                queue.add(cur.left);
                ans.add(cur.left.value);
            } else {
                ans.add(null);
            }
            if (cur.right != null) {
                queue.add(cur.right);
                ans.add(cur.right.value);
            } else {
                ans.add(null);
            }
        }
        return ans;
    }

    // 按层反序列化
    public static Node levelDes(Queue<String> levelList) {
        if (levelList == null || levelList.size() == 0) return null;
        Node head = new Node(levelList.poll(), null, null);
        Queue<Node> queue = new LinkedList<>();
        queue.add(head);
        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            String leftStr = levelList.poll();
            if (leftStr != null) {
                Node node = new Node(leftStr, null, null);
                queue.add(node);
                cur.left = node;
            }
            String rightStr = levelList.poll();
            if (rightStr != null) {
                Node node = new Node(rightStr, null, null);
                queue.add(node);
                cur.right = node;
            }
        }
        return head;
    }
}
